package com.lihepeng.leecode.solidaimoffer.array;

/**
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 */
public class Solution40 {
    /**
     * 使用堆排序的方法维护   大根堆实时维护数组
     *
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers(int[] arr, int k) {

        return null;
    }

    /**
     * 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
     * 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
     * 升序用大碓顶，降序用小堆顶
     */
    public void sort(int[] arrs) {
        // 构建大顶堆
        for (int i = arrs.length / 2 - 1; i >= 0; i--) {
            adjectHeap(arrs, i, arrs.length);
        }

    }

    private void adjectHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1]) {

            }
        }
    }

    private void swap(int[] arrs, int i, int j) {
        int temp = arrs[i];
        arrs[i] = arrs[j];
        arrs[j] = temp;

    }
}
